public class Solution264 {
    /**
     * 编写一个程序，找出第 n 个丑数。
     *
     * 丑数就是质因数只包含 2, 3, 5 的正整数。
     */
    public int nthUglyNumber(int n) {
        int[] arr = new int[n];
        arr[0] = 1;
        int i = 0, j = 0, k = 0, tem;
        for (int m = 1; m < n; m++) {
            tem = Math.min(Math.min(arr[i] * 2, arr[j] * 3), arr[k] * 5);
            arr[m] = tem;
            if (tem == arr[i] * 2) i++;
            if (tem == arr[j] * 3) j++;
            if (tem == arr[k] * 5) k++;
        }
        return arr[n - 1];
    }
}
